

class Solution1 {
    public int numSquares(int n) {
        int q = (int)Math.sqrt(n);
        int[][] dp = new int[q+1][n+1];
        for(int i = 1; i<=n; i++) dp[0][i] = 0x3f3f3f3f;
        dp[0][0] = 1;
        for(int i = 1; i<=q; i++) {
            for(int j = 1; j<=n; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= i*i) {
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-i*i] + 1);
                }
            }
        }

        return dp[q][n];
    }
}

class Solution2 {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] dp = new int[len+1][m+1][n+1];
        for(int i = 1; i<= len; i++) {
            int mm = 0, nn = 0;
            for(int t = 0; t < strs[i-1].length(); t++) {
                if(strs[i-1].charAt(t) == '0') mm++;
                else nn++;
            }
            for(int j = 1; j <= m; j++) {
                for(int k = 1; k<=n; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j >= mm && k >= nn) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j-mm][k-nn] + 1);
                    }
                }
            }
        }

        return dp[len][m][n];
    }
}


class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i<= len; i++) {
            int mm = 0, nn = 0;
            for(int t = 0; t < strs[i-1].length(); t++) {
                if(strs[i-1].charAt(t) == '0') mm++;
                else nn++;
            }
            for(int j = m; j >= mm; j--) {
                for(int k = n; k>=nn ; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j-mm][k-nn] + 1);
                }
            }
        }

        return dp[m][n];
    }
}

public class Test {
}
